package com.bo.day20231128;

import java.util.Arrays;

/**
 * 快速排序
 * leetcode：https://leetcode.cn/problems/sort-colors/description/
 * 图解：https://cloud.fynote.com/edit?nid=379571&id=1701333233024&t=1701394151170
 * 时间复杂度：O(N*logn)
 *
 * @Author: gpb
 * @Date: 2023/11/30 15:37
 * @Description:
 */
public class PartitionAndQuickSort {

    /**
     * 数组位置交换
     */
    public static void swap (int[] arr, int l, int r) {
        int t = arr[l];
        arr[l] = arr[r];
        arr[r] = t;
    }

    /**
     * 数组中的数小于arr[r] 放在左边, 大于arr[r]的放在右边,等于arr[r]放在中间,arr[r]位置和大于指针进行交换
     * 返回等于 arr[r] 数组下标范围
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int[] partition (int[] arr, int l, int r) {
        if (l > r) {
            return new int[]{-1, -1};
        }
        if (l == r) {
            return new int[]{l, r};
        }
        // 小于arr[r]范围的指针,交换一次,往右移动
        int less = l - 1;
        // 大于arr[r]范围的指针,交换一次,往左移动
        int more = r;
        // 数组指针
        int index = l;
        while (index < more) {
            if (arr[index] == arr[r]) {
                // 相等数组执政往后移动
                index++;
            } else if (arr[index] < arr[r]) {
                // 和小于指针+1位置交换
                swap(arr, index++, ++less);
                // 小于arr[r]范围的指针,交换一次,往右移动
                // 数组指针往后移动
            } else {
                // 大于
                // 和小于指针-1位置交换
                swap(arr, index, --more);
                // 大于arr[r]范围的指针,交换一次,往左移动
            }
        }
        // arr[r]位置和大于指针进行交换
        swap(arr, r, more);
        // 返回 中间相等访问数组下标
        return new int[]{less + 1, more};
    }

    public static void quickSort (int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process (int[] arr, int l, int r) {
        System.out.println("l=" + l + ",r=" + r + ",arr=" + Arrays.toString(arr));
        if (l >= r) {
            // 终止条件,起始位置>=结束位置
            return;
        }
        // 快速排序,选择的数要随机性
        swap(arr, r, l + (int) (Math.random() * (r - l + 1)));
        // 进行排序
        int[] partition = partition(arr, l, r);
        System.out.println("l=" + l + ",r=" + r + ",arr=" + Arrays.toString(arr) + ",partition=" + Arrays.toString(partition));
        // l-partition[0]-1 左部分
        process(arr, l, partition[0] - 1);
        // partition[1]+1~r 右部分
        process(arr, partition[1] + 1, r);
    }

    public static void main (String[] args) {
        int[] arr = {8, 3, 5, 1, 2, 3, 8, 3};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
